/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/the-skyline-problem
   @Language: C++
   @Datetime: 20-01-09 16:54
   */

class Solution {
public:
	/**
	 * @param buildings: A list of lists of integers
	 * @return: Find the outline of those buildings
	 */
	vector<vector<int>> buildingOutline(vector<vector<int>> &buildings) {
		// write your code here
		vector<pair<int,int> > xys;
		for(const auto &b:buildings){
			xys.push_back({b[0], -b[2]});
			xys.push_back({b[1], b[2]});
		}
		sort(xys.begin(), xys.end());
		multiset<int> heights({0});
		vector<vector<int> > vs;
		vector<int> last={0,0,0};
		for(const auto &xy:xys){
			if (xy.second<0) heights.insert(-xy.second);
			else heights.erase(heights.find(xy.second));
			int maxh = *heights.rbegin();
			if (last[2]!=maxh){
				last[0]=last[1];
				last[1]=xy.first;
				if (last[2]!=0) vs.push_back(last);
				last[2]=maxh;
			}
		}
		return vs;
	}
};
